// ===============================================================================
// scan: sequential scan of a large descriptor collection
// Created in September 2007 as a project for an Advanced Database Systems course
// (c) Reykjavik University, Björn Þór Jónsson, Kristleifur Daðason, Herwig Lejsek
// Contact author: Björn Þór Jónsson, Reykjavík University, bjorn@ru.is
// ===============================================================================

#include "QueryDescInfo.h"

QueryDescInfo::QueryDescInfo(FlexDescriptor * _query,
			     int _numDims,
			     int _nns)
{
	numDims = _numDims;
	query = _query;
	nns = _nns;

	neighbors = 0;
	farthest  = 0;
	scanNext = -1;

	identifiers = new int[nns];
	distances   = new float[nns];

	for (int i = 0; i < nns; i++)
		distances[i] = FLT_MAX;
};

QueryDescInfo::~QueryDescInfo()
{
	delete identifiers;
	delete distances;
};

void QueryDescInfo::compareAndReplaceFarthest(FlexDescriptor *data)
{
	// This is the inner-most part of the algorithm of
	// Figure 4 of the TR (inside the double loop)
	float dist = Distance(data);
	if (dist < distances[farthest]) {
		identifiers[farthest] = data->id;
		distances[farthest] = dist;
		FindFarthest();
	}
};

void QueryDescInfo::FindFarthest()
{
	// This corresponds to the algorithm of Figure 3 of the TR
	// with a small twist to cleverly solve the special case
	// of the first NN data descriptors.  Note that it is
	// efficient to check for the special case here, as this
	// code will probably not be run so often once a good
	// set of NN neighbors has been found.

	// Up to NN-1 neighbors, the farthest can simply point to
	// the first entry which has not been assigned to a neighbor
	// because they have already been initialized to FLT_MAX
	if (neighbors < nns-1) {
		neighbors++;
		farthest = neighbors;
		return;
	}

	// The remainder is the algo of Figure 3 in the TR
	neighbors = nns;
	float dist = 0;
	for (int i = 0; i < nns; i++) {
		if (distances[i] > dist) {
			dist = distances[i];
			farthest = i;
		}
	}
}

float QueryDescInfo::Distance(FlexDescriptor *data)
{
	// This is the algorithm of Figure 5 of the TR
	float dist = 0.0;
	/* * /
	for (int i=0; i<numDims; i++) {
		float dimdist = (data->dim[i] - query->dim[i]);
		dist += dimdist * dimdist;
		if (dist > distances[farthest])
			return FLT_MAX;
	}
	//*/
	/* */
	int i = 0;
	int n = (numDims + 7) / 8;
    switch (numDims % 8) {
		case 0: do { dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 7:      dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 6:      dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 5:      dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 4:      dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 3:      dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 2:      dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 1:      dist += (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		} while (--n && (dist < distances[farthest]));
    }
	//*/
	/* * /
	int i = 0;
	int n = (numDims + 7) / 8;
	int n0=0, n1=0, n2=0,n3=0,n4=0,n5=0,n6=0,n7=0;
    switch (numDims % 8) {
		case 0: do { n0 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 7:      n1 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 6:      n2 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 5:      n3 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 4:      n4 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 3:      n5 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 2:      n6 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
		case 1:      n7 = (data->dim[i] - query->dim[i]) * (data->dim[i] - query->dim[i++]);
			dist = ((n0 + n1)+((n2+n3)+((n4+n5)+(n6+n7))));
		} while (--n && (dist < distances[farthest]));
    }
	//*/
	return dist;
};

void QueryDescInfo::open()
{
	scanNext = 0;
};


int *QueryDescInfo::next()
{
	if (scanNext < neighbors)
		return &(identifiers[scanNext++]);
	return NULL;
};

void QueryDescInfo::close()
{
	scanNext = -1;
};

